class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        if (n == 0)
            return {{}};
        vector<vector<string>> res = {};
        vector<int> nums(n);
        for (int i = 0; i < n; i++)
            nums[i] = i;
        check(nums, {}, res);
        return res;
    }
    void check(vector<int> nums, vector<int> currPermutation, vector<vector<string>>& res) {
        for (int i = 0; i < nums.size(); i++)
        {
            // 非常关键！！！避免for循环时，参数发生改变（代替了回溯过程中的“全局变量恢复”部分）
            vector<int> tempNums(nums);
            vector<int> tempPermutation(currPermutation);
            
            bool valid = true;
            for (int j = 0; j < tempPermutation.size() ; j++)
            {
                if (tempPermutation.size() - j == tempNums[i] - tempPermutation[j] || tempPermutation.size() - j == tempPermutation[j] - tempNums[i])
                {
                    valid = false;
                    break;
                }
            }
            if(!valid) continue;
            tempPermutation.push_back(tempNums[i]);
            tempNums.erase(tempNums.begin() + i);
            if (tempNums.empty())
            {
                vector<string> tempV(tempPermutation.size());
                for (int k = 0; k < tempPermutation.size(); k++)
                {
                    string tempS(tempPermutation.size() - 1, '.');
                    tempS.insert(tempPermutation[k], "Q");
                    tempV[k] = tempS;
                }
                res.push_back(tempV);
                // return;
            }
            check(tempNums, tempPermutation, res);
        }
        return;
    }
};
